package test.route;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * Display all the routes for the given start station and end station
 * 
 * @author ginger
 * 
 */
public class RouteDisplayer {

	static class Station {
		String name;
		Set<Station> nextStations;

		Station(String name) {
			this.name = name;
			nextStations = new HashSet<Station>();
		}
	}

	private Map<String, Station> stationMap;

	public Map<String, Station> getStationMap() {
		return stationMap;
	}

	public RouteDisplayer() {
		stationMap = new HashMap<String, Station>();

		// construct stations graph
		InputStream is = this.getClass().getResourceAsStream("stations.csv");
		BufferedReader br = new BufferedReader(new InputStreamReader(is));
		try {
			String line = br.readLine();
			while (line != null) {
				String[] stations = line.split(",");

				if (stationMap.get(stations[0]) == null) {
					stationMap.put(stations[0], new Station(stations[0]));
				}

				Station nextStation = stationMap.get(stations[1]);
				if (nextStation == null) {
					stationMap.put(stations[1], new Station(stations[1]));
					nextStation = stationMap.get(stations[1]);
				}
				stationMap.get(stations[0]).nextStations.add(nextStation);

				line = br.readLine();
			}
		} catch (IOException e) {
			e.printStackTrace();
		}
	}

	public List<List<Station>> getRoutes(String startStationName, String endStationName) {
		Station startStation = stationMap.get(startStationName);
		Station endStation = stationMap.get(endStationName);

		if ((startStation == null) || (endStation == null)) {
			return null;
		}

		List<Station> route = new ArrayList<Station>();
		route.add(startStation);
		return findRoutes(route, startStation, endStation);
	}

	// currentStation included in currentRoute
	private List<List<Station>> findRoutes(List<Station> currentRoute, Station currentStation, Station targetStation) {
		List<List<Station>> result = new ArrayList<List<Station>>();
		if (targetStation.name.equals(currentStation.name)) {
			// found
			result.add(currentRoute);
			return result;
		} else if (currentStation.nextStations.isEmpty()) {
			// not found
			return null;
		}

		// continue search
		for (Station next : currentStation.nextStations) {
			// check existence to avoid dead loop
			if (!currentRoute.contains(next)) {
				// Copy a new sub-route for branching, o/w the same route list shared in sub-route, IMPORTANT!!!
				List<Station> myRoute = new ArrayList<Station>(currentRoute);
				myRoute.add(next);
				List<List<Station>> routes = findRoutes(myRoute, next, targetStation);
				if (routes != null) {
					result.addAll(routes);
				}
			}
		}
		return result;

	}

	public static void main(String[] args) {
		RouteDisplayer routeDisplayer = new RouteDisplayer();

		String startStation = null;
		String endStation = null;

		/* Doesn't work in Eclipse */
		// Console c = System.console();
		// startStation = c.readLine("enter start station > ");
		// endStation = c.readLine("enter end station > ");

		try {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			try {
				System.out.print("enter start station > ");
				startStation = br.readLine();
				System.out.print("enter end station > ");
				endStation = br.readLine();
			} finally {
				br.close(); // IMPORTANT!!
			}
		} catch (IOException e) {
			e.printStackTrace();
		}

		List<List<Station>> routes = routeDisplayer.getRoutes(startStation, endStation);

		if (routes == null) {
			System.out.println("No route found.");
		}
		for (List<Station> route : routes) {
			boolean first = true;
			for (Station station : route) {
				System.out.print(first ? station.name : "->" + station.name);
				first = false;
			}
			System.out.println();
		}

		// output to file
		PrintWriter fw = null;    // PrintWriter provide convenient print methods just like System.out
		try {
			fw = new PrintWriter(new BufferedWriter(new FileWriter("result.txt")));
			for (List<Station> route : routes) {
				boolean first = true;
				for (Station station : route) {
					fw.print(first ? station.name : "->" + station.name);
					first = false;
				}
				fw.println();
			}
		} catch (IOException e) {
			e.printStackTrace();
		} finally {
			if (fw != null) {
				fw.close();       // It swallow IOException, unlike BufferedReader and BufferedWriter
			}
		}
	}
}
